

// pub trait I32Key {
//     fn key(&self) -> i32;
// } 

/// 从小到大排列的有序列表
pub struct ListSortedI32<TValue> {
    keys: Vec<i32>,
    key_min: i32,
    key_max: i32,
    items: Vec<TValue>,
}


impl<TValue> ListSortedI32<TValue> {
    pub fn new() -> Self {
        Self {
            keys: vec![],
            items: vec![],
            key_min: i32::MAX,
            key_max: i32::MIN,
        }
    }
    pub fn with_capacity(capacity: usize) -> Self {
        Self {
            keys: Vec::with_capacity(capacity),
            items: Vec::with_capacity(capacity),
            key_min: i32::MAX,
            key_max: i32::MIN,
        }
    }
    pub fn len(&self) -> usize {
        self.items.len()
    }
    pub fn key_min(&self) -> i32 {
        self.key_min
    }
    pub fn key_max(&self) -> i32 {
        self.key_max
    }

    pub fn add_binary_search(&mut self, key: i32, item: TValue) -> bool {
        let index = self.len();
        if index == 0 {
            self.key_min = key;
            self.key_max = key;
            self.keys.push(key);
            self.items.push(item);

            return true;
        }
        // 1. key is less than key_min
        if key < self.key_min {
            // debug!("List_Ordered::add: 添加的 {key} 比最小值 {} 小, 插入头部0位置.", self.key_min);
            self.keys.insert(0, key);
            self.key_min = key;
        
            self.items.insert(0, item);
            return true;
        };
        // 3. key is larger than key_max
        if key > self.key_max() {
            // debug!("List_Ordered::add: 添加的 {key} 比最大值 {} 小, 添加在尾部位置.", self.key_max);
            self.keys.push(key);
            self.key_max = key;
        
            self.items.push(item);
            return true;
        }
        
        // 2. key is between key_min and key_max
        // debug!("List_Ordered::add: 出现【后发先至】{} ==> {key}, 采用插入方法", self.key_max);

        match self.keys.binary_search(&key) {
            Ok(index) => {
                error!("List_Ordered::add: 重复添加 keys[{index}] = {key}");
                false
            },
            Err(index_fail) => {
                self.keys.insert(index_fail, key);
                
                self.items.insert(index_fail, item);
                true
            },
        }

    }
    /// 
    pub fn add_iterate_from_tail(&mut self, key: i32, item: TValue) -> bool {
        let index = self.len();
        if index == 0 {
            self.key_min = key;
            self.key_max = key;
            self.keys.push(key);
            self.items.push(item);

            return true;
        }
        // 1. key is less than key_min
        if key < self.key_min {
            // debug!("List_Ordered::add: 添加的 {key} 比最小值 {} 小, 插入头部0位置.", self.key_min);
            self.keys.insert(0, key);
            self.key_min = key;
        
            self.items.insert(0, item);
            return true;
        };
        // 3. key is larger than key_max
        if key > self.key_max() {
            // debug!("List_Ordered::add: 添加的 {key} 比最大值 {} 小, 添加在尾部位置.", self.key_max);
            self.keys.push(key);
            self.key_max = key;
        
            self.items.push(item);
            return true;
        }
        
        // 2. key is between key_min and key_max
        // debug!("List_Ordered::add: 出现【后发先至】{} ==> {key}, 采用插入方法", self.key_max);
        let len = self.items.len();
        for index in (0..len).rev() {
            let key_current = self.keys[index];
            if key_current == key {
                // error!("List_Ordered::add: 重复添加 {key}");
                return false;
            }
            if key_current > key {
                continue;
            }
            // key_current < key
            // debug!("List_Ordered::add: 在 {key_current} 后面添加 {key}");
            self.keys.insert(index + 1, key);
            
            self.items.insert(index + 1, item);
            return true;
        }

        false

    }
    // fn find_plain(&self, key2find: TKey) -> Option<TValue> {
    //     for item in self.items.iter() {
    //         if key2find < item.key() {
    //             // error!("self.find_plain(key2find={}), not exists.", key2find);
    //             return None;
    //         }
    //         if key2find == item.key() {
    //             return Some(item.clone());
    //         }
    //     }
    //     // error!("self.find_plain(key2find={}), not exists.", key2find);
    //     None
    // }
    pub fn index_of(&self, key2find: i32) -> Option<usize> {
        match self.keys.binary_search(&key2find) {
            Ok(index) => Some(index),
            Err(_) => {
                // error!("self.find_binary(key2find={}), not exists.", key2find);
                // 一般来说，如果是严格的从小到大，如果存在，肯定能找到
                // self.find_plain(key2find)
                None
            },
        }
    }
    pub fn get(&self, key2find: i32) -> Option<&TValue> {
        let index = self.index_of(key2find)?;
        self.items.get(index)
    }
    pub fn get_mut(&mut self, key2find: i32) -> Option<&mut TValue> {
        let index = self.index_of(key2find)?;
        self.items.get_mut(index)
    }
    
    pub fn items(&self) -> Vec<(&i32, &TValue)> {
        let mut items = vec![];

        for (index, key) in self.keys.iter().enumerate() {
            items.push((key, &self.items[index]));
        }

        items
    }


}


#[cfg(test)]
mod tests {
    // use fasttime::b2_time::TimeFT;

    #[test]
    fn test_binary_search_01() {
        let mut list_i32 = vec![];
        let count = 10;
        for i in 0..count {
            list_i32.push(i * 2);
        }
        list_i32.insert(1, 1);
        println!("{list_i32:?}");
        for i in (-1)..(count + 1) {
            let val = i * 2 + 1;
            match list_i32.binary_search(&val) {
                Ok(index) => println!("keys[{index}]={val}"),
                Err(index_fail) => {
                    let 值 = match list_i32.get(index_fail) {
                        Some(v) => v.to_string(),
                        None => "越界".to_string(),
                    };
                    println!("{val} ==> {index_fail}: {值}");
                },
            }
        }
    }

    // #[test]
    // fn test_benchmark_listsorted32() {
    //     let name = "test_binary_search_1 普通单元测试";
    //     let cpu = "Intel(R) Xeon(R) CPU E5 2680 v3 @ 2.50GHz 2.50GHz";
    //     println!("{name}: {cpu}");
    //     for count in [10_0000, 100_0000, 1000_0000, 1_0000_0000] {
    //         let time_开始 = TimeFT::now();
    //         let list_i32 = crate::random::shuffle::generate_list_i32(0, count);
    //         let mut items = super::ListSortedI32::with_capacity(count as usize);
    //         for val in list_i32 {
    //             // items.add_iterate_from_tail(val, val);
    //             items.add_binary_search(val, val);
    //         }
    //         let time_初始化 = TimeFT::now();
    //         let secs_初始化 = time_初始化.seconds_from(&time_开始);
    //         println!("[0, {count}): {time_开始}, {secs_初始化:.3} 秒(初始化);");
    //         for key2find in 0..count {
    //             match items.index_of(key2find) {
    //                 Some(index) => assert_eq!(index as i32, key2find),
    //                 None => panic!("{name} 必须找到: {key2find} [0, {count})"),
    //             }
    //         }
    //         let time_查找 = TimeFT::now();
    //         let secs_查找 = time_查找.seconds_from(&time_初始化);
    //         let micros_每一次查找 = time_查找.micros_from(&time_初始化) as f64 / count as f64;
    //         println!("\t{secs_查找:.3} 秒(查找), 平均 {micros_每一次查找:.2} 微秒 / 每一次查找.");
    //     }
    //     /*kldn
    //     cargo test test_binary_search_1 -- --nocapture
    //     test_binary_search_1 普通单元测试: Intel(R) Xeon(R) CPU E5 2680 v3 @ 2.50GHz 2.50GHz
    //     [0, 100000): 21:47:54(506)090, 0.005 秒(初始化), 0.035 秒(查找), 平均 0.35 微秒 / 每一次查找.
    //     [0, 1000000): 21:47:54(546)126, 0.025 秒(初始化), 0.326 秒(查找), 平均 0.33 微秒 / 每一次查找.
    //     [0, 10000000): 21:47:54(897)325, 0.183 秒(初始化), 3.857 秒(查找), 平均 0.39 微秒 / 每一次查找.
    //     [0, 100000000): 21:47:58(941)093, 1.661 秒(初始化), 40.848 秒(查找), 平均 0.41 微秒 / 每一次查找.
    //     [0, 1000000000): 21:48:41(493)663, 16.706 秒(初始化), 456.158 秒(查找), 平均 0.46 微秒 / 每一次查找.
    //      */
    // }

}



pub mod temp_test {
    // use fasttime::b2_time::TimeFT;

    // pub fn test_benchmark_listsorted32() {
    //     let name = "test_binary_search_1 普通单元测试";
    //     // let cpu = "Intel(R) Xeon(R) CPU E5 2680 v3 @ 2.50GHz 2.50GHz";
    //     let cpu = "Unkown";
    //     println!("{name}: {cpu}");
    //     for count in [10_0000, 100_0000, 1000_0000, 1_0000_0000] {
    //         let time_开始 = TimeFT::now();
    //         let list_i32 = crate::random::shuffle::generate_list_i32(0, count);
    //         let mut items = super::ListSortedI32::with_capacity(count as usize);
    //         for val in list_i32 {
    //             // items.add_iterate_from_tail(val, val);
    //             items.add_binary_search(val, val);
    //         }
    //         let time_初始化 = TimeFT::now();
    //         let secs_初始化 = time_初始化.seconds_from(&time_开始);
    //         println!("[0, {count}): {time_开始}, {secs_初始化:.3} 秒(初始化);");
    //         for key2find in 0..count {
    //             match items.index_of(key2find) {
    //                 Some(index) => assert_eq!(index as i32, key2find),
    //                 None => panic!("{name} 必须找到: {key2find} [0, {count})"),
    //             }
    //         }
    //         let time_查找 = TimeFT::now();
    //         let secs_查找 = time_查找.seconds_from(&time_初始化);
    //         let micros_每一次查找 = time_查找.micros_from(&time_初始化) as f64 / count as f64;
    //         println!("\t{secs_查找:.3} 秒(查找), 平均 {micros_每一次查找:.2} 微秒 / 每一次查找.");
    //     }
    //     /*
    //     cargo test test_binary_search_1 -- --nocapture
    //     test_binary_search_1 普通单元测试: Intel(R) Xeon(R) CPU E5 2680 v3 @ 2.50GHz 2.50GHz
    //     [0, 100000): 21:47:54(506)090, 0.005 秒(初始化), 0.035 秒(查找), 平均 0.35 微秒 / 每一次查找.
    //     [0, 1000000): 21:47:54(546)126, 0.025 秒(初始化), 0.326 秒(查找), 平均 0.33 微秒 / 每一次查找.
    //     [0, 10000000): 21:47:54(897)325, 0.183 秒(初始化), 3.857 秒(查找), 平均 0.39 微秒 / 每一次查找.
    //     [0, 100000000): 21:47:58(941)093, 1.661 秒(初始化), 40.848 秒(查找), 平均 0.41 微秒 / 每一次查找.
    //     [0, 1000000000): 21:48:41(493)663, 16.706 秒(初始化), 456.158 秒(查找), 平均 0.46 微秒 / 每一次查找.
    //     */
    // }

    
}